package algothrim

import "fmt"

func knapSack(W int, wt []int, val []int, n int) int {
	fmt.Printf("W: %d, wt: %v, val: %v, n: %d", W, wt, val, n)
	fmt.Println()
	if n == 0 || W == 0 {
		return 0
	}

	if wt[n-1] > W {
		return knapSack(W, wt, val, n-1)
	} else {
		return max(val[n-1]+knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1))
	}
}

func knapSackI(w int, wt []int, val []int, n int) int {
	if n == 0 || w == 0 {
		return 0
	}

	if wt[n-1] > w {
		return knapSackI(w, wt, val, n-1)
	} else {
		return max(val[n-1]+knapSackI(w-wt[n-1], wt, val, n-1), knapSackI(w, wt, val, n-1))
	}
}

func knapSackWithBackTrace() (int, []int) {
	bestVal := 0
	w := 50
	wt := []int{10, 20, 30}
	val := []int{60, 100, 120}
	var item []int
	var bestItem []int
	var f func(cw int, cval int, n int)
	f = func(cw int, cVal int, n int) {
		if cw == w || n == len(wt) {
			if cVal >= bestVal {
				bestVal = cVal
				bestItem = make([]int, len(item))
				copy(bestItem, item)
			}
			return
		}
		f(cw, cVal, n+1) // 不放入当前物品
		if cw+wt[n] <= w {
			item = append(item, wt[n])
			f(cw+wt[n], cVal+val[n], n+1)
			item = item[:len(item)-1] // 回溯不放入物品
		}
	}
	f(0, 0, 0)
	return bestVal, bestItem
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
